package mo.leetcode_top;

import java.util.*;

public class L207 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] in = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int[] pair = prerequisites[i];
            List<Integer> targets = graph.get(pair[1]);
            if (Objects.isNull(targets)) {
                targets = new ArrayList<>();
                targets.add(pair[0]);
                graph.put(pair[1], targets);
            } else {
                targets.add(pair[0]);
            }
            in[pair[0]]++;
        }
        Stack<Integer> queue = new Stack<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                queue.push(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer val = queue.pop();
            List<Integer> integers = graph.get(val);
            if (integers != null) {
                for (int de : integers) {
                    in[de]--;
                    if (in[de] == 0) {
                        queue.push(de);
                    }
                }
            }
        }

        for (int i = 0; i < numCourses; i++) {
            if (in[i] != 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        L207 test = new L207();
        System.out.println(test.canFinish(5, new int[][]{{1, 4}, {2, 4}, {3, 1}, {3, 2}}));
    }

}
